package com.day5.t4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Main {
    /*public List<Integer> findAnagrams(String s, String p) {
        char[] charArray = p.toCharArray();
        Arrays.sort(charArray);
        String s1 = new String(charArray);
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < s.length()-p.length()+1; i++){
            char[] charArray1 = s.substring(i,i+p.length()).toCharArray();
            Arrays.sort(charArray1);
            String s2 = new String(charArray1);
            if(s1.equals(s2)){
                list.add(i);
            }
        }
        return list;
    }*/
    //统计出p中每个字符出现的次数
    //移动的时候移动窗口，左减，右加
    public static List<Integer> findAnagrams(String s, String p) {
        if(s.length() < p.length()){
            return new ArrayList<>();
        }
        int[] need = new int[26];
        int[] window = new int[26];
        List<Integer> list = new ArrayList<>();
        for(int i=0; i < p.length(); i++){
            need[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(need, window)){
            list.add(0);
        }
        for (int i = 1; i <=s.length()-p.length() ; i++) {
            window[s.charAt(i-1) - 'a']--;
            window[s.charAt(i+p.length()-1) - 'a']++;
            if(Arrays.equals(need, window)){
                list.add(i);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("baa","aa"));
    }
}
